#pragma once
using namespace std;

template <class T>
class BinaryTree
{
private:
    struct TreeNode
    {
        T value;
        TreeNode *left;
        TreeNode *right;

        TreeNode() : left(nullptr), right(nullptr) {}
        TreeNode(const T &val, TreeNode *l = nullptr, TreeNode *r = nullptr) : value(val), left(l), right(r) {}
    };
    TreeNode *m_root;                         //根结点
    void clear(TreeNode *t);                  //清空
    int size(TreeNode *t) const;              //二叉树结点总数
    int height(TreeNode *t) const;            //二叉树的高度
    int leafnum(TreeNode *t) const;           //叶子结点个数
    void preOrder(TreeNode *t) const;         //递归前序
    void inOrder(TreeNode *t) const;          //递归中序
    void postOrder(TreeNode *t) const;        //递归后序
    void preOrderCreat(T flag, TreeNode *&t); //创建二叉树

public:
    BinaryTree() : m_root(nullptr) {}                //构造函数
    ~BinaryTree() { clear(); }                       //析构
    bool empty() const { return m_root == nullptr; } //判空
    void clear()                                     //清空
    {
        if (m_root)
            clear(m_root);
        m_root = nullptr;
    }
    int size() const { return size(m_root); }       //求结点总数
    int height() const { return height(m_root); }   //求高度
    int leafnum() const { return leafnum(m_root); } //叶子结点个数
};